/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2006-2013. All rights reserved.
 ******************************************************************************************/

/******************************************************************************************
 * Test of Graph
 ******************************************************************************************/
#include "Graph_Test.h"
#include <cstring>
/******************************************************************************************
 ******************************************************************************************/
template <typename Tv, typename Te> 
GraphMatrix<Tv, Te>* randomGraph(int n, int e) { 
   GraphMatrix<char, int>* g = new GraphMatrix<char, int>;
   while ((g->n < n) || (g->e < e)) { 
      if (g->n < n) 
         if (dice(100) < 65) { 
            Tv vertex = (Tv) ('A'+dice(26));      /*DSA*/printf("Inserting vertex"); cout<<vertex; printf(" ...");
            g->insert(vertex);               /*DSA*/printf("done\n");
         } else { 
            if (1 > g->n) continue;
            int i = dice(g->n);       /*DSA*/printf("Deleting vertex %d ...", i);
            Tv v = g->remove(i);        /*DSA*/printf("done with"); cout<<v; printf("\n");
         }
      if ((1 < g->n) && (g->e < e)) 
         if (dice(100) < 65) { 
            int i = dice(g->n), j = dice(g->n); Te e = dice((Te)3*n);
                                       /*DSA*/printf("Inserting edge (%d, %d) = ", i, j); cout<<e; printf(" ...");
            if (g->exists(i, j)) {      /*DSA*/printf("already exists\n");
            } else {
               g->insert(e, e, i, j);      /*DSA*/printf("done\n");
            }
         } else { 
            int i = dice(g->n), j = dice(g->n);
                                       /*DSA*/printf("Deleting edge (%d, %d) ...", i, j);
            if (g->exists(i, j)) {
               Te e = g->remove(i, j);  /*DSA*/printf("done with"); cout<<e; printf("\n");
            } else {                   /*DSA*/printf("not exists\n");
            }
         }
   }
   for (int i = 0; i < n; i++) g->vertex(i) = 'A' + i;
   /*DSA*/GraphMatrix_print(*g);
   return g;
}


/******************************************************************************************
 ******************************************************************************************/
int main(int argc, char* argv[]) {
   srand((unsigned int)time(NULL));
   GraphMatrix<char, int>* g;
   g = randomGraph<char, int>(50,100); 
   /*DSA*/printf("\n"); GraphMatrix_print(*g);

   /*DSA*/printf("=== BFS\n");
   g->bfs(0); /*DSA*/GraphMatrix_print(*g);
   /*DSA*/printf("=== BFS (PFS)\n");
   g->pfs(0, BfsPU<char, int>()); /*DSA*/GraphMatrix_print(*g);

   /*DSA*/printf("=== DFS\n");
   g->dfs(0); /*DSA*/GraphMatrix_print(*g);
   /*DSA*/printf("=== DFS (PFS)\n");
   g->pfs(0, DfsPU<char, int>()); /*DSA*/GraphMatrix_print(*g);

   /*DSA*/printf("=== BCC\n");
   g->bcc(0); /*DSA*/GraphMatrix_print(*g);

   /*DSA*/printf("=== Prim\n");
   g->prim(0); /*DSA*/GraphMatrix_print(*g);
   /*DSA*/printf("=== Prim (PFS)\n");
   g->pfs(0, PrimPU<char, int>()); /*DSA*/GraphMatrix_print(*g);

   /*DSA*/printf("=== Dijkstra\n");
   g->dijkstra(0); /*DSA*/GraphMatrix_print(*g);
   /*DSA*/printf("=== Dijkstra (PFS)\n");
   g->pfs(0, DijkstraPU<char, int>()); /*DSA*/GraphMatrix_print(*g);

   delete g; return 0;
}
